package com.zzz.test;

import java.util.*;


public class Solution {

    public static void main(String[] args) {
        int[][] muns = new int[][]{{1, 2, 5}, {3, 2, 1}};
        String leetcode = new Solution().reverseWords("a good   example");
//        System.out.println(Math.min(1, 1));
        System.out.println(leetcode);
    }


    public String reverseWords(String s) {
        //去掉两端空格
        String trim = s.trim();
        StringBuilder sb = new StringBuilder();
        int p, q = trim.length() - 1;
        p = q;
        while (p >= 0) {
            while (p >= 0 &&' ' != trim.charAt(p)) {
                p--;
            }
            sb.append(trim.substring(p+1, q+1).trim()).append(" ");
            while (p > 0 &&' ' == trim.charAt(p)){
                p--;
            }
            q = p;
        }
        return sb.toString().trim();

    }


    //双指针  求和
    public int[] twoSum(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while (i < j) {
            if (nums[i] + nums[j] < target) {
                i++;
            } else if (nums[i] + nums[j] > target) {
                j--;
            } else {
                return new int[]{nums[i], nums[j]};
            }

        }
        return new int[0];
    }

    // 双指针
    public int[] exchange1(int[] nums) {

        int i = 0, j = nums.length - 1;
        while (i < j) {
            // 找到一个偶数
            while (i < j && (nums[i] & 1) == 1) {
                i++;
            }
            // 找到一个奇数
            while (i < j && (nums[j] & 1) == 0) {
                j--;
            }
            // 交换上面两个数的位置
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        return nums;
    }


    //
    public int[] exchange(int[] nums) {

        int count = 0;
        int n = 0;
        int length = nums.length;
        int[] newNums = new int[length];
        // 第一次遍历获取所有奇数的个数
        for (int num : nums) {
            if (num % 2 == 1) {
                count++;
            }
        }

        //第二次遍历 如果是奇数就从前面开始 如果是偶数就从中间开始
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 1) {
                newNums[n] = nums[i];
                n++;
            } else {
                newNums[count] = nums[i];
                count++;
            }
        }
        return newNums;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode A = headA, B = headB;
        // A 和 B 为null  结束不相交的情况 如果A,next == null 那么A 永远不可能为null
        // 不相交的时候就无法判断
        while (A != B) {
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }

        return A;


    }


    // 两个结点相交  map法
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        HashMap<Integer, ListNode> map = new HashMap<>();
        while (headA != null) {
            map.put(headA.val, headA);
            headA = headA.next;
        }

        while (headB != null) {
            if (map.get(headB.val) == headB) {
                break;
            }
            headB = headB.next;
        }
        return headB;
    }


    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
/*        ListNode down = new ListNode(0), head = down;
        while (l1 != null & l2 != null) {
            if (l1.val < l2.val) {
                head.next = l1;
                l1 = l1.next;
            } else {
                head.next = l2;
                l2 = l2.next;
            }
            head = head.next;
        }
        head.next = l1 == null ? l2 : l1;
        return down.next;*/
        ListNode head = new ListNode(0), cur = head;
        while (l1 != null && l2 != null) {
            ListNode node = minNode(l1, l2);
            if (node == l1) {
                l1 = l1.next;
            } else {
                l2 = l2.next;
            }
            cur.next = node;
            cur = cur.next;

        }
        cur.next = l1 == null ? l2 : l1;

        return head.next;


    }

    public ListNode minNode(ListNode l1, ListNode l2) {
        return l1.val < l2.val ? l1 : l2;
    }


    public ListNode getKthFromEnd(ListNode head, int k) {

        ListNode pre = null, cur = head;
        for (int i = 0; i < k; i++) {
            pre = head;
            head = pre.next;
        }
        while (pre.next != null) {
            pre = pre.next;
            cur = cur.next;
        }
        return cur;
    }

    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        if (head.val == val) {
            return head.next;
        }
        ListNode newHead = head;
        while (head.next != null) {
            ListNode next = head.next;
            if (next.val == val) {
                head.next = next.next;
            }
            head = next;
        }
        return newHead;

    }


    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() <= 0) {
            return 0;
        }
        int result = 0;
        int leftIndex = -1;
        HashMap<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (map.containsKey(chars[i])) {
                leftIndex = Math.max(leftIndex, map.get(chars[i]));
            }
            map.put(chars[i], i);
            result = Math.max(result, i - leftIndex);
        }
        return result;

    }


    public int translateNum(int num) {
        String value = String.valueOf(num);
        char[] chars = value.toCharArray();
        if (chars.length == 1) {
            return 1;
        }
        int p = 1, q = 1, r = 0;
        for (int i = 1; i < chars.length; i++) {
            String str = "" + chars[i - 1] + chars[i];
            r = q + isOk(i, chars) * p;
            p = q;
            q = r;
        }
        return r;

    }

    public int isOk(int i, char[] chars) {
        String str = "" + chars[i - 1] + chars[i];
        return str.compareTo("10") >= 0 && str.compareTo("25") <= 0 ? 1 : 0;
    }


    // 变态阶梯  动态规划
    public int numWays2(int n) {
        if (n == 1) {
            return 1;
        }
/*
        int MOD = 1000000007;
        int p = 1, r = 0;
        for (int i = 2; i <= n; i++) {
            r = 2 * p  % MOD;
            p = r; }
*/


        return 1 << (n - 1);


    }

    public int maxValue(int[][] grid) {
        int m = grid[0].length; //长
        int n = grid.length; //宽

        for (int i = 1; i < n; i++) {
            grid[i][0] = grid[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < m; j++) {
            grid[0][j] = grid[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
            }
        }

        return grid[n - 1][m - 1];

    }


    public int maxSubArray(int[] nums) {
        int max = nums[0];  //定义最大值
        int pre = 0;  //dp[i-1]
        int cur; //dp[i]
        for (int num : nums) {
            cur = num; // 当前值
            if (pre > 0) { //如果前一个值是正的 那么改变当前值
                cur += pre;
            }
            max = Math.max(cur, max); //比较当前值和之前的max大小
            pre = cur; //下一次循环 先前值为当前值

        }
        return max;

    }

    // 动态规划 最大利润
    public int maxProfit(int[] prices) {
        // 定义最大花费 和最大收益
        int pro = 0, cost = Integer.MAX_VALUE;
        for (int price : prices) {
            // 求最低价格
            cost = Math.min(price, cost);
            // 求最大利润
            pro = Math.max(pro, price - cost);
        }

        return pro;
    }


    // 阶梯  动态规划
    public int numWays(int n) {
        if (n < 2) {
            return 1;
        }
        int MOD = 1000000007;
        int p = 1, q = 1, r = 2;
        for (int i = 3; i <= n; i++) {
            p = q;
            q = r;
            r = (p + q) % MOD;
        }
        return r;


    }

    //斐波那契数列
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int MOD = 1000000007;
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q;
            q = r;
            r = (p + q) % MOD;

        }
        return r;

    }


    // 对称
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return symmetric(root.left, root.right);
    }

    public boolean symmetric(TreeNode l, TreeNode r) {
        if (l == null && r == null) {
            return true;
        }
        if (l == null || r == null || l.val != r.val) {
            return false;
        }
        return symmetric(l.left, r.right) && symmetric(l.right, r.left);
    }

    // 镜像树
    public TreeNode mirrorTree(TreeNode root) {

        if (root == null) {
            return null;
        }
        reverse(root);
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }

    public TreeNode reverse(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }


    //  子树
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        boolean r1 = recur(A, B);
        boolean r2 = isSubStructure(A.left, B);
        boolean r3 = isSubStructure(A.right, B);
        return r1 || r2 || r3;

    }


    public boolean recur(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        }
        if (A == null || A.val != B.val) {
            return false;
        }
        return recur(A.left, B.left) && recur(A.right, B.right);
    }


    public List<List<Integer>> levelOrder3(TreeNode root) {
        if (root == null) {
            return new LinkedList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();

        LinkedList<List<Integer>> arrayList = new LinkedList<>();
        int row = 1;
        queue.add(root);  // 头结点入队
        while (!queue.isEmpty()) {

            LinkedList<Integer> list = new LinkedList<>();
            int size = queue.size();
            // 弹出当前的所有结点
            for (int i = 0; i < size; i++) {

                TreeNode treeNode = queue.poll();
                list.add(treeNode.val);
                if (treeNode.left != null) { // 左节点不为空 加入
                    queue.add(treeNode.left);
                }
                if (treeNode.right != null) { // 右节点不为空 加入
                    queue.add(treeNode.right);
                }


            }
            if (row % 2 == 0) {
                Collections.reverse(list);
            }
            row++;

            arrayList.add(list);
        }

        return arrayList;

    }

    public List<List<Integer>> levelOrder2(TreeNode root) {
        if (root == null) {
            return new LinkedList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();

        LinkedList<List<Integer>> arrayList = new LinkedList<>();

        queue.add(root);  // 头结点入队
        while (!queue.isEmpty()) {
            LinkedList<Integer> list = new LinkedList<>();
            int size = queue.size();
            // 弹出当前的所有结点
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = queue.poll();
                list.add(treeNode.val);
                if (treeNode.left != null) { // 左节点不为空 加入
                    queue.add(treeNode.left);
                }
                if (treeNode.right != null) { // 右节点不为空 加入
                    queue.add(treeNode.right);
                }
            }

            arrayList.add(list);
        }

        return arrayList;

    }


    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<>();
        LinkedList<Integer> list = new LinkedList<>();
        queue.add(root);  // 头结点入队
        while (!queue.isEmpty()) {
            // 弹出第一个结点
            TreeNode treeNode = queue.poll();
            list.add(treeNode.val);  // 获取值
            if (treeNode.left != null) { // 左节点不为空 加入
                queue.add(treeNode.left);
            }
            if (treeNode.right != null) { // 右节点不为空 加入
                queue.add(treeNode.right);
            }
        }

        int size = list.size(); // 获取list大小 作为返回数组长度
        int[] value = new int[size];
        for (int i = 0; i < size; i++) {  // 将list中的值添加到数组中
            value[i] = list.get(i);
        }


        return value;
    }


    public char firstUniqChar(String s) {
        if (s.equals("")) {
            return " ".charAt(0);
        }
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            String re = String.valueOf(aChar);
            String replace = s.replaceFirst(re, "");
            if (!replace.contains(re)) {
                return aChar;
            }
        }
        return " ".charAt(0);
    }


    public int minArray(int[] numbers) {

        Arrays.sort(numbers);
        return numbers[0];

    }


    public boolean findNumberIn2DArray(int[][] matrix, int target) {

        int k = matrix.length;

        for (int j = 0; j < k; j++) {
            for (int i = matrix[j].length - 1; i >= 0; i--) {
                if (matrix[j][i] == target) {
                    return true;
                }
            }
        }

        return false;

    }


    public int findRepeatNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num)) {
                return num;
            }
        }
        return -1;

    }

    public int missingNumber(int[] nums) {
        int i = 0;
        for (int num : nums) {
            if (num != i) {
                return i;
            }
            i++;
        }
        return -1;
    }


    public int search(int[] nums, int target) {
        HashSet<Integer> set = new HashSet<>();
        int i = 0;
        boolean flag = false;
        for (int num : nums) {
            if (num == target) {
                if (set.add(num)) {
                    flag = true;
                    i++;
                } else {
                    i++;
                }
            }

        }
        if (flag) {
            return i;
        }
        return 0;
    }


    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        for (Node cur = head, copy = null; cur != null; cur = cur.next.next) {
            copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
        }
        for (Node cur = head; cur != null; cur = cur.next.next) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
        }
        Node newHead = head.next;
        for (Node cur = head; cur != null; cur = cur.next) {
            Node newNode = cur.next;
            cur.next = cur.next.next;
            newHead.next = newNode.next != null ? newNode.next.next : null;
        }

        if (head == null) {
            return null;
        }
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = new Node(node.val);
            nodeNew.next = node.next;
            node.next = nodeNew;
        }
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = node.next;
            nodeNew.random = (node.random != null) ? node.random.next : null;
        }
        Node headNew = head.next;
        for (Node node = head; node != null; node = node.next) {
            Node nodeNew = node.next;
            node.next = node.next.next;
            nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
        }


        return newHead;


    }

}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}